The present invention is related to data broadcasting. More particularly, the present invention relates to an improved method for information retrieval from broadcast disk systems.
In traditional client-server architectures, such as the World Wide Web, data transfers are initiated by the clients. Such an architecture is referred to as a xe2x80x9cpullxe2x80x9d system because clients, by their requests, xe2x80x9cpullxe2x80x9d data from the server. An emerging alternative to pull systems are xe2x80x9cpushxe2x80x9d systems. In push systems, the server repeatedly broadcasts or xe2x80x9cpushesxe2x80x9d data towards clients even though there is no request on the part of the clients for such data.
One type of push technology is referred to as a xe2x80x9cbroadcast disk system.xe2x80x9d In broadcast disk systems, data is divided into a number of equal-sized pages. Such pages are broadcast in a round-robin manner by a server. The name xe2x80x9cbroadcast diskxe2x80x9d derives from the broadcast schedule, which is a circular repetition of the pages. Broadcast disk systems have been in use since the early 1980s by many national television companies in Western Europe. Moreover, broadcast disks have also been used in high-throughput multiprocessor database systems over high-bandwidth networks and wireless telecommunications systems. Typical of push systems, broadcast disk systems are particularly useful for disseminating massive amounts of information to a large number of clients.
FIG. 1 depicts, figuratively, a broadcast disk system that is implemented using wireless telecommunications technology. It should be understood that a broadcast disk system may alternatively be implemented as a wireline system. The broadcast disk system comprises server 102 including appropriate radios and processors (not shown) for broadcasting information or data items on pages Pl-Pn in a broadcast cycle 104. The pages of data items are broadcast by antenna 106 to aplurality of clients, four of which clients, C1-C4, are shown in FIG. 1. The clients receive each particular page at substantially the same time.
Since the pages are broadcast according to a set schedule unrelated to a particular client""s need for a specific item of information, a client may disadvantageously have to wait a long time for desired information to be broadcast. Such a scenario is illustrated with reference to FIG. 1, which depicts server 102 broadcasting page Pj at time T1. For the purpose of the present example, it is assumed that client C1 requires, at time T1, a data item that is located on page Pi. It is evident from the illustration that client C1 will have to wait the better part of a broadcast cycle until page Pi is again broadcast.
To improve the performance (i.e., decrease the waiting time) of broadcast disk systems, client storage resources are advantageously integrated with the broadcast disk system. In particular, such storage resources allow a client to store at least some of the broadcasted pages in a local fast memory. If a page desired by the client turns out to be stored in such fast memory, such a page request can be satisfied immediately. For example, if client C1 possessed such storage capabilities, and has page Pi stored in its fast memory at time T1, the page request for page Pi will be immediately satisfied.
It will be appreciated that the storage capacity of a client""s fast memory is typically insufficient for storing all information broadcast by the broadcast disk system. As such, pages must be selectively stored. The contents of a client""s fast memory typically changes on a substantially regular basis as a client adds pages to the fast memory and evicts others to make room for the added pages. Returning to the example, if client C1 chooses not to store page Pi in its fast memory, or, if page Pi is stored but the client decides to evict it before time T1, then the client will have to wait for page Pi to be broadcast again by the server, thereby incurring a xe2x80x9ccost.xe2x80x9d
The aforementioned technique wherein client storage resources are used for storing broadcasted pages is referred to as xe2x80x9cpaging.xe2x80x9d A broadcast disk system incorporating paging is referred to as broadcast disk paging (BDP) system. A client""s objective is to reduce, to a practical minimum, the time (i.e., cost) needed to satisfy a sequence of page requests.
The prior art has utilized a paging method referred to as xe2x80x9cleast recently usedxe2x80x9d (xe2x80x9cLRUxe2x80x9d) to improve broadcast disk system performance. In the LRU method, as a page is requested it is time-stamped. The time stamp is continually updated to reflect the most recent request for each particular page. When a page fault occurs (i.e., a requested page is not in fast memory), the least recently requested page is evicted from fast memory and the requested page, once broadcast, is added thereto.
The cost, A, for a paging method can be evaluated relative to the cost, C, of an optimal paging method. In an optimal paging method, the schedule of page requests is known Thus, pages can be stored and evicted in fast memory in an xe2x80x9coptimumxe2x80x9d manner. The LRU method achieves a relatively poor competitive ratio, A/C, of O (nxc2x7k), where n is the number of pages being broadcast, k is the size of the fast memory and the notation xe2x80x9cO,xe2x80x9d referred to as xe2x80x9cbig O,xe2x80x9d or xe2x80x9con the order of,xe2x80x9d is a conventional notation defined for use herein as follows: a function ƒ (x) is said to be xe2x80x9cO (g (x))xe2x80x9d is there exists a constant, c, such that for every x, ƒ(x)xe2x89xa6cxc2x7g (x).
In view of the poor competitive ratio achieved by the aforementioned prior art paging method, the art would benefit from a new paging method having improved competitive performance.
A paging method for information retrieval from broadcast disk systems is described. In some embodiments, the present method advantageously achieves a competitive ratio of O (n log k), which is significantly better than that of the prior art LRU methods. The method proceeds in response to a page request (e.g., a request for an item of data, which request originates from a program operating on a processor). To satisfy the request in an efficient manner, a three- xe2x80x9ccolorxe2x80x9d labelling scheme is advantageously used, wherein:
(1) Fast memory is checked for the requested page.
(2) If the requested page is present in the fast memory, the request is considered to be immediately fulfilled.
If the requested page is not present in the fast memory, and
(A) if the requested page is not presently being broadcasted, and
(i) if the page being broadcasted is xe2x80x9cgrey,xe2x80x9d indicating that it has xe2x80x9csomewhat recentlyxe2x80x9d been requested, then the grey page is stored in fast memory;
(ii) if the page being broadcasted is xe2x80x9cwhite,xe2x80x9d indicating that is has not been requested in some time, then the page is not added to fast memory.
(B) if the requested page is presently being broadcasted, it is re-labelled as xe2x80x9cblackxe2x80x9d and added to fast memory.
As a black- or grey-labelled page is added to fast memory, the grey-labelled page that is xe2x80x9cleast expensivexe2x80x9d to reload into fast memory is evicted therefrom to make room for the added page, as required.
(3) When fast memory is filled with black-labelled pages, all grey-labelled pages (none of which will be in fast memory) are re-labelled as xe2x80x9cwhitexe2x80x9d to indicate that they have not been requested in quite some time, and all black-labelled pages are relabelled as xe2x80x9cgreyxe2x80x9d indicating that they have recently been requested. The method then repeats, adding and evicting pages as appropriate.
The operation wherein xe2x80x9cgreyxe2x80x9d (i. e., non-requested) pages are added to fast memory while waiting for the requested page to be broadcasted is referred to herein as xe2x80x9cprefetching.xe2x80x9d Prefetching in accordance with the present teachings advantageously adds a xe2x80x9chighest-costxe2x80x9d page to fast memory. By way of explanation, each non-requested page, at the completion of its broadcast, is a xe2x80x9chighest-costxe2x80x9d page because it will take a complete broadcast cycle until that page is rebroadcasted. In accordance with the present teachings, if such a xe2x80x9chighest-costxe2x80x9d page is a grey-labelled page indicating that is has recently been requested, it is advantageously added to fast memory since, in accordance with the present method, a grey-labelled page is more likely to be requested than a white-labelled page. If a page is requested immediately after it is broadcast, and such a page is not present in fast memory, the highest possible cost (longest wait for re-broadcasting) is incurred.
Assuming that the fast memory is full, a page must be evicted to allow a page to be added thereto. In accordance with the present teachings, the grey-labelled page in fast memory that is the least expensive to replace (of all such stored, grey-labelled pages) is advantageously evicted from fast memory. The least expensive page to replace is the page that, according to the broadcast schedule, will be re-broadcast first. Thus, if that page is requested immediately after its eviction from fast memory, a lower cost is incurred in waiting for that page to be rebroadcast as compared to grey-labelled pages in fast memory.
By virtue of the three-xe2x80x9ccolorxe2x80x9d labelling scheme and prefetching operation, the present method takes into account the relative expense or cost of pages, unlike the LRU method of the prior art. By doing so, the present method achieves a significantly better competitive ratio than the prior art.
It will be understood that the label designations used herein (i.e., black, grey and white), are arbitrarily chosen. Any labelling scheme may be used.